翻訳と辞書 Words near each other ・ Longest bridge ・ Longest climbing salamander ・ Longest common subsequence problem ・ Longest common substring problem ・ Longest Day ・ Longest Day of Nelson ・ Longest element of a Coxeter group ・ Longest English sentence ・ Longest fence in the world ・ Longest increasing subsequence ・ Longest linear sequence ・ Longest NCAA Division I football winning streaks ・ Longest Night ・ Longest Night Service ・ Longest palindromic substring ・ Longest path problem ・ Longest prefix match ・ Longest professional baseball game ・ Longest recorded sniper kills ・ Longest reigning heavyweight champions ・ Longest repeated substring problem ・ Longest rivers of the United Kingdom ・ Longest squash match records ・ Longest tennis match records ・ Longest tiebreaker in tennis ・ Longest train services ・ Longest trains ・ Longest uncrossed knight's path ・ Longest word in English ・ Longest word in Spanish Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Longest path problem ： ウィキペディア英語版 Longest path problem In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or (in weighted graphs) by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard, meaning that it cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems. ==NP-hardness== The NP-hardness of the unweighted longest path problem can be shown using a reduction from the Hamiltonian path problem: a graph ''G'' has a Hamiltonian path if and only if its longest path has length ''n'' − 1, where ''n'' is the number of vertices in ''G''. Because the Hamiltonian path problem is NP-complete, this reduction shows that the decision version of the longest path problem is also NP-complete. In this decision problem, the input is a graph ''G'' and a number ''k''; the desired output is "yes" if ''G'' contains a path of ''k'' or more edges, and ''no'' otherwise.〔.〕 If the longest path problem could be solved in polynomial time, it could be used to solve this decision problem, by finding a longest path and then comparing its length to the number ''k''. Therefore, the longest path problem is NP-hard. It is not NP-complete, because it is not a decision problem.〔.〕 In weighted complete graphs with non-negative edge weights, the weighted longest path problem is the same as the Travelling salesman path problem, because the longest path always includes all vertices.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Longest path problem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.